package leetcode_day._2022._202203._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/13 16:43
 * UTF-8 编码验证
 * 算法：位运算 + 模拟
 * 根据当前元素判断这个字符是 n 个字节
 * 然后再判断这个元素后的 n - 1 个元素是否满足条件
 */
public class _13_393 {

    public boolean validUtf8(int[] data) {
        int len = data.length;
        for (int i = 0; i < len;) {
            int j = 7;
            while (j >= 0 && (data[i] >> j & 1) == 1) --j;
            // cnt 表示这个元素后应该跟几个字节
            int cnt = 7 - j;
            // 对于 1 字节 的字符，字节的第一位设为 0; 一个字符可能的长度为 1 到 4 字节
            if (cnt == 1 || cnt > 4) return false;
            // 超过了数组大小
            if (i + cnt - 1 >= len) return false;
            for (int k = i + 1; k < i + cnt; k++) if ((data[k] >> 7 & 1) != 1 || (data[k] >> 6 & 1) != 0) return false;
            if (cnt == 0) ++i;
            else i += cnt;
        }
        return true;
    }

}
